package graph

// createDirectedGraphMatrix 创建一个有向图的邻接矩阵表示。
// 参数 n 表示图中节点的数量。
// 参数 edges 是一个二维整数数组，其中每个元素包含两个整数，表示图中的一条有向边，从第一个整数对应的节点指向第二个整数对应的节点。
// 返回值是一个二维整数数组，表示图的邻接矩阵表示，其中 ans[i][j] = 1 表示存在一条从节点 i 到节点 j 的有向边，否则 ans[i][j] = 0。
func createDirectedGraphMatrix(n int, edges [][]int) [][]int {
	// 初始化邻接矩阵，大小为 n * n，所有元素默认初始化为 0。
	ans := make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, n)
	}

	// 遍历 edges，将有向边的信息记录在邻接矩阵中。
	for i := range edges {
		ans[edges[i][0]][edges[i][1]] = 1
	}

	// 返回构建好地邻接矩阵。
	return ans
}

// createDirectedGraphLinked 创建一个有向图的邻接表表示。
// 参数 n 表示图中节点的数量，
// edges 是一个二维整数数组，表示图中的边，
// 每个元素 edges[i] = [ui, vi] 表示有一条从 ui 到 vi 的有向边。
// 返回值是图的邻接表表示形式，其中 ans[i] 表示节点 i 所连接的所有节点的列表。
func createDirectedGraphLinked(n int, edges [][]int) [][]int {
	// 初始化邻接表，初始时每个节点都没有连接的节点
	ans := make([][]int, n)

	// 遍历边的数组，构建邻接表
	for i := range edges {
		// 对于每条边，将边的终点添加到起点的连接节点列表中
		beginPointId := edges[i][0]
		endPointId := edges[i][1]
		beginPointConnectedNodes := &ans[beginPointId]
		*beginPointConnectedNodes = append(*beginPointConnectedNodes, endPointId)
	}

	// 返回构建好地邻接表表示的有向图
	return ans
}

// createUndirectedGraphMatrix 创建一个无向图的邻接矩阵表示。
// 参数 n 表示图中节点的数量，edges 是一个二维数组，每个元素表示图中的一条边，由两个节点的索引组成。
// 返回值是一个二维数组，表示图的邻接矩阵。
func createUndirectedGraphMatrix(n int, edges [][]int) [][]int {
	// 初始化邻接矩阵，大小为 n*n，初始值为0。
	ans := make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, n)
	}

	// 遍历边集，构建无向图的邻接矩阵。
	for i := range edges {
		// 无向图中，如果存在节点 edges[i][0] 到 edges[i][1] 的边，那么也在 edges[i][1] 到 edges[i][0] 之间存在边。
		ans[edges[i][0]][edges[i][1]] = 1
		ans[edges[i][1]][edges[i][0]] = 1
	}

	// 返回构建好地邻接矩阵。
	return ans
}

// createUndirectedGraphLinked 创建一个无向图的邻接表表示。
// 参数 n 表示图中节点的数量，edges 是一个二维数组，表示图中的边。
// 每个边由一对节点索引组成，表示这两个节点之间有一条边。
// 返回值是一个二维数组，其中每个元素是一个列表，包含了与该节点直接相连的所有节点的索引。
func createUndirectedGraphLinked(n int, edges [][]int) [][]int {
	// 初始化邻接表，初始时每个节点的邻接列表为空。
	// ans[i] 表示节点 i 的邻接列表。
	ans := make([][]int, n)

	// 遍历所有边，构建邻接表。
	for i := range edges {
		// 对于每条边，将其两个节点添加到彼此的邻接列表中。
		// 这是因为在无向图中，节点 v 和节点 w 互相邻接。
		point1 := edges[i][0]
		point2 := edges[i][1]
		ans[point1] = append(ans[point1], point2)
		ans[point2] = append(ans[point2], point1)
	}

	// 返回构建好地邻接表。
	return ans
}

// createDirectedGraphMatrixWithWeight 创建一个有向加权图的邻接矩阵表示。
// 参数 n 表示图中节点的数量。
// 参数 edges 是一个二维整数数组，其中每个元素包含三个整数[a, b, w]，
// 表示从节点a到节点b存在一条权重为w的有向边。
// 返回值为一个二维整数数组，表示根据edges定义的有向加权图的邻接矩阵。
func createDirectedGraphMatrixWithWeight(n int, edges [][]int) [][]int {
	// 初始化邻接矩阵，大小为n*n，所有元素默认初始化为0。
	// ans[i][j]表示从节点i到节点j的边的权重，默认为0。
	ans := make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, n)
	}

	// 遍历edges数组，根据edges中的边和权重信息填充邻接矩阵。
	for i := range edges {
		point1 := edges[i][0]
		point2 := edges[i][1]
		weight := edges[i][2]
		ans[point1][point2] = weight
	}

	// 返回填充完成的邻接矩阵。
	return ans
}

// createDirectedGraphLinkedWithWeight 创建一个有向图，该图由节点和带权重的边组成。
// 参数n表示图中节点的数量，edges是一个二维整数数组，每个子数组包含三个整数，
// 分别表示边的起点、终点和边的权重。
// 返回值是一个二维整数数组，表示图的邻接表表示形式，其中每个节点都关联到一个
// 由其相邻节点及边的权重组成的列表。
func createDirectedGraphLinkedWithWeight(n int, edges [][]int) [][][]int {
	// 初始化图的邻接表表示，大小为n，初始值为空。
	// ans[i]表示节点i的邻接列表，每个元素是一个长度为2的整数数组，
	// ans[i][j][0]表示相邻节点，ans[i][j][1]表示权重。
	ans := make([][][]int, n)

	// 遍历所有边，构建邻接表。
	for i := range edges {
		// 将边的信息（终点节点和权重）添加到起点节点的邻接列表中。
		point1 := edges[i][0]
		point2 := edges[i][1]
		weight := edges[i][2]
		ans[point1] = append(ans[point1], []int{point2, weight})
	}

	// 返回构建好的图的邻接表表示。
	return ans
}

// createUndirectedGraphMatrixWithWeight 生成无向图的邻接矩阵表示，其中包含边的权重。
// n 表示图中节点的数量。
// edges 是一个二维整数数组，每个元素表示图中的一条边，包含两个节点的索引和这条边的权重。
// 返回值是一个二维整数数组，表示无向图的邻接矩阵，其中非零元素表示节点间边的权重。
func createUndirectedGraphMatrixWithWeight(n int, edges [][]int) [][]int {
	// 初始化邻接矩阵，大小为n*n，全部元素默认初始化为0。
	ans := make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, n)
	}

	// 遍历edges数组，构建无向图的邻接矩阵。
	// 由于是无向图，对于每条边，需要在邻接矩阵的两个方向上都记录边的权重。
	for i := range edges {
		ans[edges[i][0]][edges[i][1]] = edges[i][2]
		ans[edges[i][1]][edges[i][0]] = edges[i][2]
	}

	// 返回构建完成的无向图邻接矩阵。
	return ans
}

// createUndirectedGraphLinkedWithWeight 创建一个无向带权图的邻接表表示。
// 参数 n 表示图中节点的数量，edges 是一个二维整数数组，每个元素表示图中的一条边，
// 其中 edges[i] = [a, b, w] 表示节点 a 和节点 b 之间存在一条权值为 w 的边。
// 返回值是一个二维整数数组，表示图的邻接表表示，其中每个节点都关联到一个
// 由与其相邻的节点及其权值组成的数组。
func createUndirectedGraphLinkedWithWeight(n int, edges [][]int) [][][]int {
	// 初始化邻接表，大小为 n，每个元素初始为空。
	ans := make([][][]int, n)

	// 遍历边的列表，构建无向图的邻接表。
	for i := range edges {
		// 对于边 edges[i] = [a, b, w]，将 b 和权值 w 添加到节点 a 的邻接列表中，
		// 同时也将 a 和权值 w 添加到节点 b 的邻接列表中，因为是无向图。
		ans[edges[i][0]] = append(ans[edges[i][0]], []int{edges[i][1], edges[i][2]})
		ans[edges[i][1]] = append(ans[edges[i][1]], []int{edges[i][0], edges[i][2]})
	}

	// 返回邻接表表示的无向图。
	return ans
}
